package com.since.algorithm.sort;

import java.util.Arrays;

/**
 * Created by Sincerity on 2020/5/15.
 * 描述： 桶排序
 * 桶排序 {@link #bucketSort(int[])}
 * 1.遍历一次数组找到数组中最小的元素,判断最小元素是否小于0
 * 2.小于0则需要给数组中的所有元素加上最小数的绝对值
 * 3.遍历找到数组的最大值,并判断最大值的位数
 * 4.找到数组元素的个位数,放入到桶里,然后根据桶的位置取出桶中存放的数组元素
 * 5.再一次根据最大值的位数循环放到捅,取出元素, 知道循环结束
 * 6.判断最小值是不是负数,如果是负数则需要对数组中所有元素减去最小值得绝对值
 */
class BucketSort {
    public static void main(String[] args) {
        int[] array = {53, 3, 111, 542, 120, 500};
        System.out.println("原数组:" + Arrays.toString(array));
        bucketSort(array);
        System.out.println("排序后:" + Arrays.toString(array));
    }

    private static void bucketSort(int[] array) {
        int max = array[0];
        int min = array[0];
        //得到数组中的最小值
        for (int item : array) {
            if (item < min) {
                min = item;
            }
        }
        //判断最小数是不是负数
        boolean flag = min < 0;
        if (flag) {
            //将数组中的负数全部加上最小的负数
            for (int i = 0; i < array.length; i++) {
                array[i] = array[i] + Math.abs(min);
            }
        }
        //得到数组中的最大值
        for (int value : array) {
            if (value > max) {
                max = value;
            }
        }
        //判断最大数的位数
        int maxLength = (max + "").length();
        //创建桶 二维数组中包含10个一位数组
        int[][] bucket = new int[10][array.length];
        //用于记录10个桶中的元素个数
        int[] bucketElementCount = new int[10];
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            for (int value : array) {
                //求数组中的个位数
                int digitsElement;
                if (value == 0) {
                    digitsElement = 0;
                } else {
                    digitsElement = value / n % 10;
                }
                //然后放入对应的个位数桶中
                bucket[digitsElement][bucketElementCount[digitsElement]] = value;
                bucketElementCount[digitsElement]++;
            }
            int index = 0;
            //取出二维数组的数
            for (int k = 0; k < bucketElementCount.length; k++) {
                if (bucketElementCount[k] != 0) {
                    for (int l = 0; l < bucketElementCount[k]; l++) {
                        array[index++] = bucket[k][l];
                    }
                }
                //清空数组
                bucketElementCount[k] = 0;
            }
        }
        if (flag) {
            for (int i = 0; i < array.length; i++) {
                array[i] = array[i] - Math.abs(min);
            }
        }
    }
}
